package org.example.sort;

/**
 * 堆排序
 * 大顶堆：L[i] >= L[2i] && L[i] >= L[2i+1]
 * 小顶堆：L[i] <= L[2i] && L[i] <= L[2i+1]
 * 其中 i >= 1 && i <= n / 2
 */
public class HeapSort {

    public void sort(int[] data) {
        // 建立大顶堆
        buildMaxHeap(data);
        // i指针指向最后一个元素的下标
        for (int i = data.length - 1; i > 1; i--) {
            swap(data, 1, i);
            adJustHead(data, 1, i - 1);
        }
    }

    /**
     * 元素交换
     * @param data
     * @param i
     * @param j
     */
    private void swap(int[] data, int i, int j) {
        int temp = data[i];
        data[i] = data[j];
        data[j] = temp;
    }

    /**
     * 建立大顶堆
     * A元素的存储序号从1开始， 。
     *
     * @param data
     */
    public void buildMaxHeap(int[] data) {
        int len = data.length - 1;
        for (int i = len / 2; i > 0; i--) {
            adJustHead(data, i, len); // 从后往前调整所有的非叶子节点
        }
    }

    /**
     * 将根节点为k的子树调整为大顶堆（元素下坠的过程）。
     * k为元素的下标。
     * A元素的存储序号从1开始，0号位为哨兵。
     *
     * @param data
     * @param k
     */
    public void adJustHead(int[] data, int k, int len) {
        // 保存哨兵的值
        int temp = data[0];
        data[0] = data[k]; // A[0]暂存子树的根节点
        for (int i = 2 * k; i <= len; i *= 2) {
            // i < len保证k有右孩子
            if (i < len && data[i] < data[i + 1]) { // 沿K较大的子节点向下筛选
                i++; // 取k较大的子节点的下标
            }
            if (data[0] >= data[i]) {
                break; // 筛选结束
            }
            data[k] = data[i]; // 将A[i]调整到父节点上
            k = i; // 修改k的值以便继续向下筛选
        }
        data[k] = data[0]; // 被筛选节点的值放入最终位置
        // 重置哨兵的值s
        data[0] = temp;
    }
}
